home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / lib / clip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-03  |  3.3 KB  |  125 lines
  1. /*
  2.  *    @(#) clip.c 9.1 93/06/14 SCOINC
  3.  *
  4.  * Written by rr@sco.com 25-May-1993
  5.  * - performs clipping of line segments wrt a window in 2-D
  6.  */
  7.  
  8. /*
  9.  * The Cohen-Sutherland clipping algorithm from pages 146-149 of the book
  10.  * "Fundamentals of Interactive Computer Graphics" by Foley and Van Dam.
  11.  * This algorithm is especially efficient when it is usually the case that
  12.  * the entire line segment to be drawn lies either inside or outside
  13.  * of the window (trivial acceptance or rejection). The algorithm relies on
  14.  * assigning each endpoint a four-bit code as follows :
  15.  *
  16.  *    1001 | 1000 | 1010
  17.  *   ------|------|------
  18.  *    0001 | 0000 | 0010
  19.  *   ------|------|------
  20.  *    0101 | 0100 | 0110
  21.  *
  22.  * with the center square above representing the window. I have altered the
  23.  * algorithm slightly to test for trivial acceptance first, followed by a
  24.  * check for trivial rejection (my most common case is trivial acceptance).
  25.  *
  26.  * The clipping routine is called clipline() and is called as follows :
  27.  * 
  28.  * clipline(points, xmin, xmax, ymin, ymax);
  29.  * where points is an XSegment containing the two endpoints of the segment
  30.  * to be drawn, xmin and ymin represent the window minimums and xmax and ymax
  31.  * the window maximums. The clipline() routine returns an XSegment containing
  32.  * the endpoints of the clipped segment.
  33.  */
  34.  
  35. #include <X11/Xlib.h>
  36.  
  37. reject_check(a, b)
  38. int *a;
  39. int *b;
  40. {
  41.     static int i;
  42.  
  43.     for (i=0;i<4;i++)
  44.         if (a[i] && b[i]) /*both endpts above, below, left, or right of window*/
  45.             return(1);
  46.     return(0);
  47. }
  48.  
  49. accept_check(a, b)
  50. int *a;
  51. int *b;
  52. {
  53.     static int i;
  54.  
  55.     for (i=0; i<4; i++)
  56.         if (a[i] || b[i]) /* at least one endpoint not in window */
  57.             return(0);
  58.     return(1);
  59. }
  60.  
  61. outcodes(x, y, xmin, xmax, ymin, ymax, out)
  62. int x, y, xmin, xmax, ymin, ymax;
  63. int *out;
  64. {
  65.     out[0] = out[1] = out[2] = out[3] = 0;
  66.     if (y > ymax)
  67.         out[0] = 1;
  68.     if (y < ymin)
  69.         out[1] = 1;
  70.     if (x > xmax)
  71.         out[2] = 1;
  72.     if (x < xmin)
  73.         out[3] = 1;
  74. }
  75.  
  76. XSegment
  77. clipline(pts,xmin,xmax,ymin,ymax)
  78. XSegment pts;
  79. int xmin, xmax, ymin, ymax;
  80. {
  81.     int outcode1[4], outcode2[4];
  82.     int accept, reject, done, tmp;
  83.  
  84.     accept = reject = done = 0;
  85.  
  86.     for(;;) {
  87.         outcodes(pts.x1, pts.y1, xmin, xmax, ymin, ymax, outcode1);
  88.         outcodes(pts.x2, pts.y2, xmin, xmax, ymin, ymax, outcode2);
  89.         accept = accept_check(outcode1, outcode2); /*check trivial accept*/
  90.         if (accept) done = 1;
  91.         else {    /* first check trivial reject */
  92.             reject = reject_check(outcode1, outcode2); /*check trivial reject*/
  93.             if (reject) done = 1;
  94.             else { /* at most one endpoint is inside */
  95.                 /* first, if P1 is inside window, exchange points 1 and 2 */
  96.                 /* and their outcodes to guarantee that P1 is outside window */
  97.                 if(!(outcode1[0] || outcode1[1] || outcode1[2] || outcode1[3])){
  98.                     tmp = pts.x1; pts.x1 = pts.x2; pts.x2 = tmp;
  99.                     tmp = pts.y1; pts.y1 = pts.y2; pts.y2 = tmp;
  100.                 }
  101.                 /* move P1 to  the intersection point */
  102.                 if (outcode1[0]) {
  103.                     pts.x1=pts.x1+(pts.x2-pts.x1)*(ymax-pts.y1)/(pts.y2-pts.y1);
  104.                     pts.y1 = ymax;
  105.                 }
  106.                 else if (outcode1[1]) {
  107.                     pts.x1=pts.x1+(pts.x2-pts.x1)*(ymin-pts.y1)/(pts.y2-pts.y1);
  108.                     pts.y1 = ymin;
  109.                 }
  110.                 else if (outcode1[2]) {
  111.                     pts.y1=pts.y1+(pts.y2-pts.y1)*(xmax-pts.x1)/(pts.x2-pts.x1);
  112.                     pts.x1 = xmax;
  113.                 }
  114.                 else if (outcode1[3]) {
  115.                     pts.y1=pts.y1+(pts.y2-pts.y1)*(xmin-pts.x1)/(pts.x2-pts.x1);
  116.                     pts.x1 = xmin;
  117.                 }
  118.             }
  119.         }
  120.         if (done)
  121.             break;
  122.     }
  123.     return(pts);
  124. }
  125.